Hãng được thành lập vào tháng 5 năm 2008 với tên gọi ban đầu là Công ty Cổ phần Hàng không Tăng Tốc, với tên giao dịch AirSpeedUp JSC, với vốn điều lệ ban đầu là 200 tỷ đồng. Tuy nhiên, chỉ một thời gian ngắn sau đó, ngày 17 tháng 10 năm 2008, hãng đã được đổi tên thành Công ty Cổ phần Hàng không Đông Dương, bởi cái tên cũ bằng tiếng Việt Tăng Tốc, được viết không dấu trở thành Tang Toc (có thể hiểu là tang tóc), là một cái tên không may theo nhạc sĩ Hà Dũng [3].

Trước đó, hãng đã từng đặt vấn đề mua lại thương hiệu Viet Airways mà Jetstar Pacific Airlines sở hữu từ năm 2006 đến nay. Tuy nhiên, cuộc thương thuyết bất thành do Jetstar Pacific Airlines tuyên bố giữ lại cái tên này để dùng vào việc khác, có thể là thành lập thêm một hãng hàng không nữa.